昨天介紹完1D的動態規劃，原本是打算繼續和大家分享2D的動態規劃和經典題型。但是考慮到連續相同的主題有些乏味而且隔個幾天再介紹動態規劃，讓大腦在這期間消化相關的知識，而不是連續好幾天都是專注在一樣的主題上，長期來看對學習比較有效率喔（我看書上說的）。
因此今天就來講解大學在學資料結構會介紹的第一個主題，Linked list。

Leetcode 206. Reverse Linked List

這是一題很常被拿來牛刀小試的題目，但是我們可以學習裡面相關的coding技巧，並且把他應用在更複雜的題目上。

題目敘述：給予某個linked list的head，將整個linked list反轉，並且回傳反轉後的新head。

分析：

• 我們需要有個指標（變數）指向目前正在拜訪的節點
• 因為要反轉linked list，我們需要讓目前拜訪的節點指向他的前一個節點，所以我們需要另一個指標去指向前一個節點。
• 我們還需要一個變數去紀錄原本節點下一個要拜訪的節點。
• 利用回圈去完整的拜訪完整條linked list。

以Python程式碼實作：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev, cur = None, head
        while cur:
            tmp = cur.next
            cur.next = prev
            prev = cur
            cur = tmp
        
        return prev

注意：我們將紀錄前一個節點的指標prev初始化為None，所以反轉後cur會指向None。因此可以推論出如果將prev初始為別的node，則最後cur會指向這個node，請先記住這個「特性」。

Leetcode 25. Reverse Nodes in k-Group

是上一題的困難版，也是指標錯綜複雜酚亂飛舞的一題。

題目敘述：給予某個linked list的head，並且每k個list node就必須被反轉，若是剩餘的list node不足k個則忽略。回傳新的linked list的head。

示意圖（擷取自leetcode）

從示意圖中可以看到「1, 2」先被反轉、「3, 4」接著被反轉，最後因為只剩一個node所以不反轉。

分析：

• 我們需要有兩個指標紀錄從哪個節點到哪個節點是要被反轉的。來標記出起點和第k個節點。
• 原本的起點在被反轉後會連向第k個節點的下一個節點，這裡可以應用到上一題我們提到的「特性」，我們讓prev指向第k個節點的下一個節點。而curr指向起點。反轉完後cur指向原先prev指的地方。
• 除了要顧及被reverse的group他們和之後的節點要怎麼連節，也要考慮在起點之前的節點也就是上一個iteration完成了反轉後，該group的最後一個節點。我們以groupPrev來指向他。而這個節點則指向curr。
• 在反轉後groupPrev所指向的節點依舊指向了curr，我們需要讓他指向被反轉後成為起點的原先是第k個的節點。
• 另外，反轉的終止條件是curr指到下一個group的第一個節點，所以我們也需要一個指標指著（跟prev指向相同的節點）

反轉前：

反轉後：

調整指標，準備下一輪的反轉：

以Python程式碼實作：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        groupPrev = dummy

        while True:
            kth = self.traverse(groupPrev, k)
            if not kth:
                break
            
            curr = groupPrev.next
            groupNext = kth.next
            prev = groupNext
            while curr != groupNext:
                tmp = curr.next
                curr.next = prev
                prev = curr
                curr = tmp
            
            tmp = groupPrev.next
            groupPrev.next = kth
            groupPrev = tmp
        
        return dummy.next
    
    def traverse(self, node, k):
        while node and k > 0:
            node = node.next
            k -= 1
        return node

注意：為了讓第一個節點不要成為edge case，所以使用了dummy node（無意義的節點），這可以幫助我們在coding上少操點心。

Leetcode 146. LRU Cache

本題是Linked List題型在Leetcode中統計出最常考的題目。想挑戰外商公司的話一定要弄熟這題。

題目敘述：

（圖源來自Leetcode）

LRU的機制就是到達了容量後最不活躍的item就會被替換掉，或是某個item更新或被存取了，該item就會變成目前最活躍的item。

分析：

• 關於get()，為了能在constant time去存取，我們需要使用到hash table，利用key:ListNode，來快速的存取到節點。在存去到該節點後，這個節點需要變成最活躍的節點。
• 關於put()，我們要去檢查這個key是否在hash table中。如果key在hash table中，那麼就需要去更新節點的值，並且讓他能夠變成最活躍的節點。相反若是沒有在hash table中，就新增一組key:ListNode，並且讓新節點成為最活躍的節點。最後，要檢查目前的hash table長度是否超過capacity，如果超過的話，我們要將最不活躍的節點刪去。
• 基於上述兩點：
  1.我們需要可以輕易地去存取到最活躍的節點和最不活躍的節點，所以我們可以利用兩個dummy node去指向這兩種節點。
  2.除此之外，我們需要常常更動到linked list，並且我們都是透過hash table來知道要更動的節點，比起traverse到該節點，不如直接將ListNode設定成有兩個指標，可以指向節點的前一個節點和下一個節點，形成double linked list。
  3.另外我們要刪除最不活躍的節點時，除了讓dummy node直接和「最不活躍的節點的下一個節點」互相指向彼此外，還需要將最不活躍的節點從hash table中刪除，所以我們的ListNode應該也要有紀錄key的attribue。這樣當我們得知最不活躍的節點時，可以馬上知道他的key，再直接去hash table將其刪除。

檢查hash table發現超過容量，決定刪除L指向的最不活躍的起點

L和該節點的下一個節點互相指向對方；從最不活躍的節點找出他的key去hash table終將他刪除。

以Python程式碼實作

class ListNode:
    def __init__(self, key = -1, val = -1):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class LRUCache:

    def __init__(self, capacity: int):
        self.cap = capacity
        self.left = ListNode()
        self.right = ListNode()
        self.left.next = self.right
        self.right.prev = self.left
        self.table = {}

    def get(self, key: int) -> int:
        if key in self.table:
            node = self.table[key]
            prev = node.prev
            prev.next = node.next
            node.next.prev = prev
            recent = self.right.prev
            recent.next, node.prev = node, recent
            self.right.prev, node.next = node, self.right
            return node.val

        return -1


    def put(self, key: int, value: int) -> None:
        if key in self.table:
            node = self.table[key]
            node.val = value
            prev = node.prev
            prev.next = node.next
            node.next.prev = prev
            recent = self.right.prev
            recent.next, node.prev = node, recent
            self.right.prev, node.next = node, self.right

        else:
            self.table[key] = ListNode(key, value)
            recent = self.right.prev
            recent.next, self.table[key].prev = self.table[key], recent
            self.table[key].next, self.right.prev = self.right, self.table[key]
        
        if len(self.table) > self.cap:
            node = self.left.next
            self.left.next, node.next.prev = node.next, self.left
            del self.table[node.key]
            


# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

後記：Fake confident looks identically to real confident. 如果在解題前先看在youtube解題的大佬的影片後，假裝自己就像大佬在解題時會不會解得比較順？